package problems.daily;

import java.util.HashMap;
import java.util.Map;

/**
 * 982. 按位与为零的三元组
 * <p>https://leetcode.cn/problems/triples-with-bitwise-and-equal-to-zero/</p>
 *
 * @author habitplus
 * @since 2023/3/4 10:06
 */
public class DT982 {
    // 哈希表 + 子集优化
    public int countTriplets1(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> cntMap = new HashMap<>();
        // 枚举前两个数
        for (int a : nums) {
            for (int b : nums) {
                cntMap.put(a & b,
                        cntMap.getOrDefault(a & b, 0) + 1);
            }
        }

        // 0 & 任意数都是 0
        int res = n * cntMap.getOrDefault(0, 0);
        // 枚举第三个数
        for (int c : nums) {
            c = c ^ 0xffff;
            for (int k = c; k != 0; k = (k - 1) & c) {
                res += cntMap.getOrDefault(k, 0);
            }
        }

        return res;
    }

    public int countTriplets(int[] nums) {
        int n = nums.length;
        // 数组代表哈希表
        int[] cntMap = new int[1 << 16]; // 65536
        // 枚举前两个数
        for (int a : nums) {
            for (int b : nums) {
                ++cntMap[a & b];
            }
        }

        // 0 & 任意数都是 0
        int res = n * cntMap[0];
        // 枚举第三个数
        for (int c : nums) {
            c = c ^ 0xffff;
            for (int k = c; k != 0; k = (k - 1) & c) {
                res += cntMap[k];
            }
        }

        return res;
    }
}
